home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung 2 / Power-Programmierung CD 2 (Tewi)(1994).iso / gnu / gnulib / ghostscr / gvirtmem.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-12-31  |  11.4 KB  |  383 lines
  1. /* Copyright (C) 1989, 1990 Aladdin Enterprises.  All rights reserved.
  2.    Distributed by Free Software Foundation, Inc.
  3.  
  4. This file is part of Ghostscript.
  5.  
  6. Ghostscript is distributed in the hope that it will be useful, but
  7. WITHOUT ANY WARRANTY.  No author or distributor accepts responsibility
  8. to anyone for the consequences of using it or for whether it serves any
  9. particular purpose or works at all, unless he says so in writing.  Refer
  10. to the Ghostscript General Public License for full details.
  11.  
  12. Everyone is granted permission to copy, modify and redistribute
  13. Ghostscript, but only under the conditions described in the Ghostscript
  14. General Public License.  A copy of this license is supposed to have been
  15. given to you along with Ghostscript so you can know your rights and
  16. responsibilities.  It should be in a file named COPYING.  Among other
  17. things, the copyright notice and this notice must be preserved on all
  18. copies.  */
  19.  
  20. /* gvirtmem.c */
  21. /* Software virtual memory for bitmaps for Ghostscript */
  22. #include <stdio.h>
  23. #include "std.h"
  24. #include "memory_.h"
  25. #include "string_.h"
  26. #include "gvirtmem.h"
  27.  
  28. /* Things that aren't in stdio.h (at least on some systems) */
  29. extern char *mktemp(P1(char *));
  30. #ifndef SEEK_SET
  31. #  define SEEK_SET 0
  32. #endif
  33.  
  34. /* Define the scratch file name for the paging file. */
  35. #ifdef __MSDOS__
  36. #  define SCRATCH_TEMP "_gvm_XXXXXX"
  37. #else
  38. #  define SCRATCH_TEMP "/tmp/gvmem_XXXXXX"
  39. #endif
  40.  
  41. /* Forward declarations */
  42. private int vmem_get_page(P3(gx_vmem *, char **, int));
  43. private int vmem_choose_page(P2(gx_vmem *, int));
  44. private void vmem_read_page(P2(gx_vmem *, int));
  45. private void vmem_write_page(P2(gx_vmem *, int));
  46. private void vmem_annul_page(P2(gx_vmem *, int));
  47. private void vmem_assign_page(P3(gx_vmem *, int, char *));
  48. private FILE *vmem_file(P1(gx_vmem *));
  49. private void vmem_seek(P2(gx_vmem *, int));
  50.  
  51. /* ------ Public interface ------ */
  52.  
  53. /* Initialize an instance of virtual memory */
  54. int
  55. vmem_init(register gx_vmem *vmem,
  56.   char **lines, int line_size, int num_lines, char init_value,
  57.   int page_size, long max_memory,
  58.   proc_alloc_t alloc, proc_free_t free)
  59. {    char *exists;
  60.     vmem->lines = lines;
  61.        {    int lnum;
  62.         for ( lnum = 0; lnum < num_lines; lnum++ )
  63.             lines[lnum] = NO_LINE;
  64.        }
  65.     if ( page_size < line_size ) page_size = line_size;
  66.     vmem->line_size = line_size;
  67.     vmem->num_lines = num_lines;
  68.     vmem->init_value = init_value;
  69.     vmem->page_size = page_size / line_size * line_size;
  70.     vmem->alloc = alloc;
  71.     vmem->free = free;
  72.     vmem->file = NULL;        /* open when needed */
  73.     vmem->lines_per_page = page_size / line_size;
  74.     vmem->num_pages =
  75.         (num_lines + vmem->lines_per_page - 1) / vmem->lines_per_page;
  76.     vmem->next_file_page = 0;
  77.     vmem->num_in_memory = 0;
  78.     vmem->max_in_memory = (int)(max_memory / page_size);
  79.  
  80.     /* Allocate and initialize the page existence table */
  81.     exists = (*alloc)(vmem->num_pages, 1, "vmem_init(exists)");
  82.     if ( exists == NULL )
  83.        {    dprintf("Couldn't allocate page status table (vmem_init)\n");
  84.         exit(1);
  85.        }
  86.     vmem->exists = exists;
  87.     memset(exists, 0, vmem->num_pages);
  88.     vmem->num_reads = 0;
  89.     vmem->num_writes = 0;
  90.  
  91.     return 0;
  92. }
  93.  
  94. /* Close the instance, deallocating the buffers and removing the */
  95. /* temporary file.  This doesn't deallocate the instance itself: */
  96. /* that is the client's responsibility.  The instance must be */
  97. /* initialized before it can be used again. */
  98. int
  99. vmem_close(register gx_vmem *vmem)
  100. {    proc_free_t free = vmem->free;
  101.     /* We deallocate in the reverse order of allocating, */
  102.     /* in the hope of pacifying a LIFO memory manager.... */
  103.     if ( vmem->file != NULL )
  104.        {    fclose(vmem->file);
  105.         vmem->file = NULL;
  106.         remove(vmem->filename);
  107.         (*free)(vmem->filename, strlen(vmem->filename)+1, 1,
  108.             "vmem_close(filename)");
  109.         vmem->filename = NULL;
  110.        }
  111.        {    /* Deallocate the buffers in a random order, */
  112.         /* and hope for the best. */
  113.         int pnum;
  114.         for ( pnum = 0; pnum < vmem->num_pages; pnum++ )
  115.            {    char *page = page_ptr(vmem, pnum);
  116.             if ( page != NO_LINE )
  117.                 (*free)(page, 1, vmem->page_size, "vmem_close(page)");
  118.            }
  119.        }
  120.     (*free)(vmem->exists, vmem->num_pages, 1, "vmem_close(exists)");
  121.     return 0;
  122. }
  123.  
  124. /* Make a page resident in memory.  Return 0 normally. */
  125. /* If the page doesn't exist, then if force is true, */
  126. /* allocate and clear the page and return 0; if force is false, */
  127. /* do nothing and return 1. */
  128. int
  129. vmem_bring_in_page(register gx_vmem *vmem, char **pline, int force)
  130. {    int fault;
  131.     if ( *pline != NO_LINE ) return 0;    /* false alarm */
  132.     vmem->lock_first = 0, vmem->lock_last = -1;    /* no lock */
  133.     fault = vmem_get_page(vmem, pline, force);
  134.     if ( fault < 0 )
  135.        {    dprintf1("vmem_get_page failed in vmem_bring_in_page, lnum = %d!\n",
  136.             pline - vmem->lines);
  137.         exit(1);
  138.        }
  139.     return 0;
  140. }
  141.  
  142. /* Make a rectangle resident in memory.  Return 0 normally. */
  143. /* If this isn't possible, return -2 to indicate to the caller */
  144. /* that it should divide the rectangle along the Y axis and try again. */
  145. /* (See the description of bring_in_proc in gxdevmem.h for details.) */
  146. int
  147. vmem_bring_in_rect(gx_vmem *vmem, int ignore_x, int lnum,
  148.   int ignore_w, int lcount, int writing)
  149. {    char **lines = vmem->lines;
  150.     int lpp = vmem->lines_per_page;
  151.     int line_first = (lnum / lpp) * lpp;    /* first line on page */
  152.     int line_last = lnum + lcount - 1;
  153.     register char **pl = lines + line_first;
  154.     char **pl_last = lines + line_last;
  155.     /* Prevent pages from being thrown out once they're in. */
  156.     vmem->lock_first = line_first / lpp;
  157.     vmem->lock_last = line_last / lpp;
  158.     for ( ; pl <= pl_last; pl += lpp )
  159.       if ( *pl == NO_LINE && vmem_get_page(vmem, pl, 1) != 0 )
  160.         return -2;
  161.     return 0;
  162. }
  163.  
  164. /* ------ Private code ------ */
  165.  
  166. /* Bring in a single page.  The caller has set lock_first and lock_last. */
  167. private int
  168. vmem_get_page(gx_vmem *vmem, char **pline, int force)
  169. {    int lnum = pline - vmem->lines;
  170.     int pnum = lnum / vmem->lines_per_page;
  171.     int clear_it = 0;
  172.     char *page;
  173.     if ( !vmem->exists[pnum] )
  174.        {    if ( !force ) return 1;
  175.         clear_it = 1;
  176.        }
  177.     if ( vmem->num_in_memory < vmem->max_in_memory &&
  178.          (page = (*vmem->alloc)(1, vmem->page_size, "vmem_get_page")) != NULL
  179.        )
  180.        {    vmem->num_in_memory++;
  181.        }
  182.     else                /* fully allocated, or can't alloc */
  183.        {    int purge_pnum = vmem_choose_page(vmem, pnum);
  184.         if ( purge_pnum < 0 ) return purge_pnum;
  185.         page = page_ptr(vmem, purge_pnum);
  186.         vmem_write_page(vmem, purge_pnum);
  187.         vmem_annul_page(vmem, purge_pnum);
  188.        }
  189.     vmem_assign_page(vmem, pnum, page);
  190.     if ( clear_it )
  191.        {    memset(page, vmem->init_value, vmem->page_size);
  192.         vmem->exists[pnum] = 1;
  193.        }
  194.     else
  195.         vmem_read_page(vmem, pnum);
  196.     return 0;
  197. }
  198.  
  199. /* Choose a page to purge.  This always succeeds, unless */
  200. /* we are bringing in a rectangle and pages are locked. */
  201. private int /* page # */
  202. vmem_choose_page(register gx_vmem *vmem, int pnum)
  203. {    /* Search for an allocated page, starting with the one */
  204.     /* farthest away from the one being read in. */
  205.     int bottom = 0, top = vmem->num_pages - 1;
  206.     while ( bottom <= top )
  207.        {    if ( pnum - bottom > top - pnum )
  208.            {    if ( page_ptr(vmem, bottom) != NO_LINE &&
  209.                  (bottom < vmem->lock_first ||
  210.                   bottom > vmem->lock_last)
  211.                )
  212.               return bottom;
  213.             bottom++;
  214.            }
  215.         else
  216.            {    if ( page_ptr(vmem, top) != NO_LINE &&
  217.                  (top < vmem->lock_first ||
  218.                   top > vmem->lock_last)
  219.                )
  220.               return top;
  221.             top--;
  222.            }
  223.        }
  224.     return -1;            /* no unlocked page */
  225. }
  226.  
  227. /* Read a page from the disk. */
  228. /* The memory page is already allocated. */
  229. private void
  230. vmem_read_page(register gx_vmem *vmem, int pnum)
  231. {    char *page = page_ptr(vmem, pnum);
  232.     FILE *file = vmem_file(vmem);
  233.     vmem_seek(vmem, pnum);
  234.     if ( fread((void *)page, sizeof(char), vmem->page_size, file)
  235.         != vmem->page_size )
  236.        {    dprintf1("fread failed in vmem_read, pnum = %d!\n",
  237.             pnum);    
  238.         exit(1);
  239.        }
  240.     vmem->num_reads++;
  241. }
  242.  
  243. /* Write a page to the disk */
  244. private void
  245. vmem_write_page(register gx_vmem *vmem, int pnum)
  246. {    char *page = page_ptr(vmem, pnum);
  247.     if ( page != NO_LINE )
  248.        {    FILE *file = vmem_file(vmem);
  249.         while ( pnum > vmem->next_file_page )
  250.            {    int count;
  251.             char value = vmem->init_value;
  252.             vmem_seek(vmem, vmem->next_file_page);
  253.             for ( count = vmem->page_size; count > 0; count-- )
  254.                 putc(value, file);
  255.             vmem->next_file_page++;
  256.            }
  257.         vmem_seek(vmem, pnum);
  258.         if ( fwrite((void *)page, sizeof(char), vmem->page_size, file)
  259.             != vmem->page_size )
  260.            {    dprintf1("fwrite failed in vmem_write, pnum = %d!\n",
  261.                 pnum);    
  262.             exit(1);
  263.            }
  264.         if ( pnum == vmem->next_file_page )
  265.             vmem->next_file_page++;
  266.        }
  267.     vmem->num_writes++;
  268. }
  269.  
  270. /* Mark a page as not in memory. */
  271. private void
  272. vmem_annul_page(register gx_vmem *vmem, int pnum)
  273. {    int lnum = pnum * vmem->lines_per_page;
  274.     char **ppage = &vmem->lines[lnum];
  275.     int limit = min(lnum + vmem->lines_per_page, vmem->num_lines);
  276.     while ( lnum++ < limit ) *ppage = NO_LINE;
  277. }
  278.  
  279. /* Mark a page as in memory. */
  280. /* The page must have been marked not in memory before. */
  281. private void
  282. vmem_assign_page(register gx_vmem *vmem, int pnum, char *page)
  283. {    int lnum = pnum * vmem->lines_per_page;
  284.     char **ppage = &vmem->lines[lnum];
  285.     char *line = page;
  286.     int limit = min(lnum + vmem->lines_per_page, vmem->num_lines);
  287.     while ( lnum++ < limit )
  288.         *ppage++ = line,
  289.         line += vmem->line_size;
  290. }
  291.  
  292. /* Open the virtual memory file if needed */
  293. private FILE *
  294. vmem_file(gx_vmem *vmem)
  295. {    FILE *file = vmem->file;
  296.     if ( file == NULL )        /* first time, open the file */
  297.        {    char *fname = (*vmem->alloc)(strlen(SCRATCH_TEMP)+1, 1,
  298.                          "vmem_file(filename)");
  299.         if ( fname == NULL )
  300.            {    dprintf("Can't alloc vmem temporary file name\n");
  301.             exit(1);
  302.            }
  303.         strcpy(fname, SCRATCH_TEMP);
  304.         if ( mktemp(fname) == NULL )
  305.            {    dprintf("Can't create vmem temporary file\n");
  306.             exit(1);
  307.            }
  308.         file = fopen(fname, "w+b");
  309.         if ( file == NULL )
  310.            {    dprintf1("Can't open vmem temporary file %s\n",
  311.                 fname);
  312.             exit(1);
  313.            }
  314.         vmem->file = file;
  315.         vmem->filename = fname;
  316.        }
  317.     return file;
  318. }
  319.  
  320. /* Seek to a given page */
  321. private void
  322. vmem_seek(gx_vmem *vmem, int pnum)
  323. {    if ( fseek(vmem_file(vmem), (long)pnum * vmem->page_size, SEEK_SET) )
  324.        {    dprintf1("fseek failed in vmem_seek, pnum = %d!\n",
  325.             pnum);
  326.         exit(1);
  327.        }
  328. }
  329.  
  330. /* ------ Test program ------ */
  331.  
  332. #ifdef VMDEBUG
  333.  
  334. #include "malloc_.h"
  335.  
  336. char *talloc(unsigned size, char *str)
  337. {    return (char *)malloc(size);
  338. }
  339. void tfree(char *blk, unsigned size, char *str)
  340. {    free(blk);
  341. }
  342.  
  343. #define MY_LINE_SIZE 8
  344. #define MY_NUM_LINES 14
  345. #define MY_PAGE_SIZE 25
  346. #define MY_MAX_MEMORY (MY_PAGE_SIZE*2)
  347. gx_vmem my_vmem;            /* static so we can print it */
  348. char *my_lines[MY_NUM_LINES];        /* ditto */
  349.  
  350. main()
  351. {    /* Following may be enabled if necessary
  352.         trace(vmem_read_page, "read", NULL, 0);
  353.         trace(vmem_write_page, "write", NULL, 0);
  354.         trace(vmem_annul_page, "annul", NULL, 0);
  355.         trace(vmem_assign_page, "assign", NULL, 0);
  356.         trace(talloc, "alloc", "%d from %s", 4);
  357.         trace(tfree, "free", "%lx %d from %s", 0);
  358.      */
  359.     vmem_init(&my_vmem, my_lines, MY_LINE_SIZE, MY_NUM_LINES, 0xbd,
  360.       MY_PAGE_SIZE, (long)MY_MAX_MEMORY, talloc, tfree);
  361.        {    /* Simple write/read loop test */
  362.         int lnum;
  363.         for ( lnum = 0; lnum < MY_NUM_LINES; lnum++ )
  364.            {    if ( my_lines[lnum] == NO_LINE )
  365.                 vmem_get_page(&my_vmem, &my_lines[lnum], 1);
  366.             my_lines[lnum][3] = lnum;
  367.            }
  368.         for ( lnum = 0; lnum < MY_NUM_LINES; lnum++ )
  369.            {    if ( my_lines[lnum] == NO_LINE )
  370.                 vmem_get_page(&my_vmem, &my_lines[lnum], 1);
  371.             if ( my_lines[lnum][3] != lnum )
  372.                 printf("Error: lnum=%d, data=%d\n",
  373.                     lnum, my_lines[lnum][3]);
  374.            }
  375.        }
  376.     vmem_close(&my_vmem);
  377.     printf("Test completed, num_reads=%ld, num_writes=%ld\n",
  378.         my_vmem.num_reads, my_vmem.num_writes);
  379.     exit(0);
  380. }
  381.  
  382. #endif                    /* ifdef VMDEBUG */
  383.